package queue;

import java.util.*;

/**
 * 滑动窗口最大值
 */
public class SlidingWindowMaximum {

  class Solution3 {

    MaxQueue queue = new MaxQueue();

    public int[] maxSlidingWindow(int[] nums, int k) {
      if (nums == null || nums.length == 0) {
        return null;
      }
      int[] ans = new int[nums.length - k + 1];
      for (int i = 0; i < k; ++i) {
        queue.push_back(nums[i]);
      }
      ans[0] = queue.max_value();
      int index = 1;
      for (int j = k; j < nums.length; ++j) {
        queue.pop_front();
        queue.push_back(nums[j]);
        ans[index++] = queue.max_value();
      }
      return ans;
    }

    /**
     * 优化版
     */
    class MaxQueue {
      private Queue<Integer> queue;
      private Deque<Integer> maxQueue;

      public MaxQueue() {
        queue = new LinkedList<Integer>();
        maxQueue = new LinkedList<Integer>();
      }

      public int max_value() {
        if (maxQueue.isEmpty()) {
          return -1;
        }
        return maxQueue.peekFirst();
      }

      public void push_back(int value) {
        while (!maxQueue.isEmpty() && maxQueue.peekLast() < value) {
          maxQueue.pollLast();
        }
        maxQueue.offerLast(value);
        queue.offer(value);
      }

      public int pop_front() {
        if (queue.isEmpty()) {
          return -1;
        }
        int ans = queue.poll();
        if (ans == maxQueue.peekFirst()) {
          maxQueue.pollFirst();
        }
        return ans;
      }
    }

  }

  /**
   * 使用双端队列
   * 当前的数比队列中的最大值都大时，将所有元素都移出栈，当前值作为最大值
   * 当前的数比队列中的最大值小时，将该元素添加到队尾
   * 经过一番操作：位于对头的元素是整个窗口中的最大值
   */
  class Solution2 {

    /**
     * Deque中存储的是数字
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
      if (nums == null || nums.length == 0) {
        return null;
      }
      Deque<Integer> deque = new LinkedList<>();
      int[] array = new int[nums.length - k + 1];
      int index = 0;
      for (int i = 0; i < nums.length; ++i) {
        //不能只通过deque的size大小来判断是否需要remove队头的元素
        //这样的做法欠妥，应该是存入数组的下标，而不是存入数组的值
        //TODO 感觉用nums[i - k] == deque.peekFirst()来判断窗口中的元素是否大于窗口的容量有点勉强
        if (deque.size() >= k || ((i >= k) && (nums[i - k] == deque.peekFirst()))) {
          deque.removeFirst();
        }
        while (!deque.isEmpty() && nums[i] > deque.peekLast()) {
          deque.pollLast();
        }
        deque.addLast(nums[i]);
        if (i >= k - 1) {
          array[index++] = deque.peekFirst();
        }
      }
      return (nums.length < k) ? new int[]{deque.peekFirst()} : array;
    }

      /**
       * 改进版:Deque中存储的是元素的下标
       *
       * @param nums
       * @param k
       * @return
       */
      public int[] maxSlidingWindo2(int[] nums, int k) {
          if (nums == null || nums.length == 0) {
              return null;
          }
          Deque<Integer> deque = new LinkedList<>();
          int[] array = new int[nums.length - k + 1];
          int index = 0;
          for (int i = 0; i < nums.length; ++i) {
              //当deque为空时,deque.peekFirst()返回null
              if (!deque.isEmpty() && ((i - deque.peekFirst()) >= k)) {
                  deque.removeFirst();
              }
              while (!deque.isEmpty() && (nums[i] > nums[deque.peekLast()])) {
                  deque.pollLast();
              }
              //offerLast:插入成功返回true,插入失败可能会返回false(因容量问题插入失败会返回false,其它问题也会抛出异常)
              //addLast:插入失败直接抛出异常
              deque.offerLast(i);
              if (i >= k - 1) {
                  array[index++] = nums[deque.peekFirst()];
              }
          }
          return (nums.length < k) ? new int[] { deque.peekFirst() } : array;
      }
  }


  /**
   * 使用sort进行排序取最大值
   * 超时
   */
  class Solution1 {

      public int[] maxSlidingWindow(int[] nums, int k) {
          if (nums == null || nums.length == 0) {
              return null;
          }
          //当数组长度小于窗口长度时，直接返回数组中的最大值
          if (nums.length < k) {
              Arrays.sort(nums);
              return new int[] { nums[nums.length - 1] };
          }
          int start = 0, numsLength = nums.length, index = 0;
          int[] array = new int[numsLength - k + 1];
          while ((start + k - 1) < numsLength) {
              int end = start + k - 1;
              int max = findSlindingWindowMaxValue(nums, start, end);
              array[index++] = max;
              start++;
          }
          return array;
      }

      private int findSlindingWindowMaxValue(int[] nums, int start, int end) {
          int tmpLength = end - start + 1;
          int[] tmpArray = new int[tmpLength];
          int j = 0;
          for (int i = start; i <= end; ++i) {
              tmpArray[j++] = nums[i];
          }
          //从小到大进行排序，最大值则是数组最后一个元素
          Arrays.sort(tmpArray);
          return tmpArray[tmpLength - 1];
      }
  }
}
